package Leetcode;

import java.util.HashMap;
import java.util.Map;

class solution_001 {
	public int[] twoSum(int[] nums, int target) {
		int i, j = 0;
		a: for (i = 0; i < nums.length; i++) {
			for (j = i + 1; j < nums.length; j++) {
				if (nums[i] + nums[j] == target) {
					// System.out.println("["+ i + "," + j + "]");
					break a;
				}
			}
		}
		return new int[] { i, j };
	}
}

// 注意到方法一的时间复杂度较高的原因是寻找 target - x
// 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。
// 使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。
// 这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

public class Solution001 {
	public static void main(String[] args) {
		Map<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
		hashmap.put(1, 0);
		hashmap.put(2, 1);
		hashmap.put(4, 2);
		// 遍历输出hashmap
		for (int i : hashmap.keySet()) {
			System.out.println(hashmap.get(i).toString() + "@" + i);
		}
	}

	public int[] twoSum(int[] nums, int target) {
		Map<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
		for (int i = 0; i < nums.length; i++) {
			if (hashmap.containsKey(target - nums[i])) {
				return new int[] { hashmap.get(target - nums[i]), i };
			}
			hashmap.put(nums[i], i);// 放在后面是因为防止6=3+3返回相同下标的情况。
		}
		return new int[0];
	}
}
